package 动态规划.斐波那契数列;

public class 打家劫舍_198 {

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }
        int N = nums.length;
        /*比如这里长度为N+1=4，那么最后返回的是dp[3]。因为下数组长度为4.下标就为0，1，2，3。
            最后返回的就是dp[3]，其实就是数组中的最后一个
        */
        int[] dp = new int[N + 1];

        //base case
        dp[0] = 0;
        dp[1] = nums[0];
        dp[2] = Math.max(nums[0], nums[1]);

        for (int i = 3; i <= N; i++) {
            //状态转移方程
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }

        return dp[N];
    }
}
